SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Rabin–Karp algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Rabin–Karp algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><caption class="infobox-title">Rabin-Karp algorithm</caption><tbody><tr><th scope="row" class="infobox-label">Class</th><td class="infobox-data"><a href="String-searching_algorithm" title="String-searching algorithm">String searching</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn)}</annotation>

</semantics>

</math></span><img src="./89ea09572a098b4762141a22c43a7ba1c20051cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.018ex; height:2.843ex;" alt="{\displaystyle O(mn)}" loading="lazy"></span> plus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m)}</annotation>

</semantics>

</math></span><img src="./a0ffd498cf521ce19814e6b7053f1f8ebb1d3c88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.623ex; height:2.843ex;" alt="{\displaystyle O(m)}" loading="lazy"></span> preprocessing time</td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Average</a> <a href="Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math></span><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"></span></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Space_complexity" title="Space complexity">space complexity</a></th><td class="infobox-data"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math></span><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"></span></td></tr></tbody></table>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, the <b>Rabin–Karp algorithm</b> or <b>Karp–Rabin algorithm</b> is a <a href="String-searching_algorithm" title="String-searching algorithm">string-searching algorithm</a> created by <a href="Richard_M._Karp" title="Richard M. Karp">Richard M. Karp</a> and <a href="Michael_O._Rabin" title="Michael O. Rabin">Michael O. Rabin</a> (<a href="#CITEREFKarpRabin1987">1987</a>) that uses <a href="Hash_function" title="Hash function">hashing</a> to find an exact match of a pattern string in a text. It uses a <a href="Rolling_hash" title="Rolling hash">rolling hash</a> to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions. Generalizations of the same idea can be used to find more than one match of a single pattern, or to find matches for more than one pattern.

</p><p>To find a single match of a single pattern, the <a href="Expected_time" class="mw-redirect" title="Expected time">expected time</a> of the algorithm is <a href="Linear_time" class="mw-redirect" title="Linear time">linear</a> in the combined length of the pattern and text,

although its <a href="Worst-case_complexity" title="Worst-case complexity">worst-case time complexity</a> is the product of the two lengths. To find multiple matches, the expected time is linear in the input lengths, plus the combined length of all the matches, which could be greater than linear. In contrast, the <a href="Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick algorithm</a> can find all matches of multiple patterns in worst-case time and space linear in the input length and the number of matches (instead of the total length of the matches).

</p><p>A practical application of the algorithm is <a href="Plagiarism_detection" class="mw-redirect" title="Plagiarism detection">detecting plagiarism</a>. Given source material, the algorithm can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single-string searching algorithms are impractical.

</p>

<div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2></div>

<p>A naive string matching algorithm compares the given pattern against all positions in the given text. Each comparison takes time proportional to the length of the pattern,

and the number of positions is proportional to the length of the text. Therefore, the worst-case time for such a method is proportional to the product of the two lengths.

In many practical cases, this time can be significantly reduced by cutting short the comparison at each position as soon as a mismatch is found, but this idea cannot guarantee any speedup.

</p><p>Several string-matching algorithms, including the <a href="Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a> and the <a href="Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a>, reduce the worst-case time for string matching by extracting more information from each mismatch, allowing them to skip over positions of the text that are guaranteed not to match the pattern. The Rabin–Karp algorithm instead achieves its speedup by using a <a href="Hash_function" title="Hash function">hash function</a> to quickly perform an approximate check for each position, and then only performing an exact comparison at the positions that pass this approximate check.

</p><p>A hash function is a function which converts every string into a numeric value, called its <i>hash value</i>; for example, we might have <code>hash("hello")=5</code>. If two strings are equal, their hash values are also equal. For a well-designed hash function, the inverse is true, in an approximate sense: strings that are unequal are very unlikely to have equal hash values. The Rabin–Karp algorithm proceeds by computing, at each position of the text, the hash value of a string starting at that position with the same length as the pattern. If this hash value equals the hash value of the pattern, it performs a full comparison at that position.

</p><p>In order for this to work well, the hash function should be selected randomly from a family of hash functions that are unlikely to produce many <a href="False_positive" class="mw-redirect" title="False positive">false positives</a>, that is, positions of the text which have the same hash value as the pattern but do not actually match the pattern. These positions contribute to the running time of the algorithm unnecessarily, without producing a match. Additionally, the hash function used should be a <a href="Rolling_hash" title="Rolling hash">rolling hash</a>, a hash function whose value can be quickly updated from each position of the text to the next. Recomputing the hash function from scratch at each position would be too slow.

</p>

<div class="mw-heading mw-heading2"><h2 id="The_algorithm">The algorithm</h2></div>

<p>The algorithm is as shown:

</p>

<div class="mw-highlight mw-highlight-lang-php mw-content-ltr mw-highlight-lines" dir="ltr"><pre><span class="k">function</span> <span class="nf">RabinKarp</span><span class="p">(</span><span class="nx">string</span> <span class="nx">s</span><span class="p">[</span><span class="mf">1.</span><span class="o">.</span><span class="nx">n</span><span class="p">],</span> <span class="nx">string</span> <span class="nx">pattern</span><span class="p">[</span><span class="mf">1.</span><span class="o">.</span><span class="nx">m</span><span class="p">])</span>

<span class="nx">hpattern</span> <span class="o">:=</span> <span class="nb">hash</span><span class="p">(</span><span class="nx">pattern</span><span class="p">[</span><span class="mf">1.</span><span class="o">.</span><span class="nx">m</span><span class="p">]);</span>

<span class="k">if</span> <span class="nx">hs</span> <span class="o">=</span> <span class="nx">hpattern</span>

<span class="k">if</span> <span class="nx">s</span><span class="p">[</span><span class="nx">i</span><span class="o">..</span><span class="nx">i</span><span class="o">+</span><span class="nx">m</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="nx">pattern</span><span class="p">[</span><span class="mf">1.</span><span class="o">.</span><span class="nx">m</span><span class="p">]</span>

<span class="hll"> <span class="k">return</span> <span class="nx">i</span>

</span> <span class="k">return</span> <span class="k">not</span> <span class="nx">found</span>

</pre></div>

<p>Lines 2, 4, and 6 each require <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">O</a>(<i>m</i>) time. However, line 2 is only executed once, and line 6 is only executed if the hash values match, which is unlikely to happen more than a few times. Line 5 is executed O(<i>n</i>) times, but each comparison only requires constant time, so its impact is O(<i>n</i>). The issue is line 4.

</p><p>Naively computing the hash value for the substring <code>s[i+1..i+m]</code> requires O(<i>m</i>) time because each character is examined. Since the hash computation is done on each loop, the algorithm with a naive hash computation requires O(<i>mn</i>) time, the same complexity as a straightforward string matching algorithm. For speed, the hash must be computed in constant time. The trick is the variable <code>hs</code> already contains the previous hash value of <code>s[i..i+m-1]</code>. If that value can be used to compute the next hash value in constant time, then computing successive hash values will be fast.

</p><p>The trick can be exploited using a <a href="Rolling_hash" title="Rolling hash">rolling hash</a>. A rolling hash is a hash function specially designed to enable this operation. A trivial (but not very good) rolling hash function just adds the values of each character in the substring. This rolling hash formula can compute the next hash value from the previous value in constant time:

</p>

<pre>s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

</pre>

<p>This simple function works, but will result in statement 5 being executed more often than other more sophisticated rolling hash functions such as those discussed in the next section.

</p><p>Good performance requires a good hashing function for the encountered data. If the hashing is poor (such as producing the same hash value for every input), then line 6 would be executed O(<i>n</i>) times (i.e. on every iteration of the loop). Because character-by-character comparison of strings with length <i>m</i> takes O(<i>m</i>) time, the whole algorithm then takes a worst-case O(<i>mn</i>) time.

</p>

<div class="mw-heading mw-heading2"><h2 id="Hash_function_used">Hash function used</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Rabin_fingerprint" title="Rabin fingerprint">Rabin fingerprint</a></div>

<p>The key to the Rabin–Karp algorithm's performance is the efficient computation of <a href="Hash_value" class="mw-redirect" title="Hash value">hash values</a> of the successive substrings of the text. The <a href="Rabin_fingerprint" title="Rabin fingerprint">Rabin fingerprint</a> is a popular and effective rolling hash function. The hash function described here is not a Rabin fingerprint, but it works equally well. It treats every substring as a number in some base, the base being usually the size of the character set.

</p><p>For example, if the substring is "hi", the base is 256, and prime modulus is 101, then the hash value would be

</p>

<pre> [(104 × 256 ) %<sup id="cite_ref-mod_1-0" class="reference"><a href="#cite_note-mod-1"><span class="cite-bracket">[</span>a<span class="cite-bracket">]</span></a></sup> 101 + 105] % 101 = 65

(<a href="ASCII" title="ASCII">ASCII</a> of 'h' is 104 and of 'i' is 105)

</pre>

<p>Technically, this algorithm is only similar to the true number in a non-decimal system representation, since for example we could have the "base" less than one of the "digits". See <a href="Hash_function" title="Hash function">hash function</a> for a much more detailed discussion. The essential benefit achieved by using a <a href="Rolling_hash" title="Rolling hash">rolling hash</a> such as the Rabin fingerprint is that it is possible to compute the hash value of the next substring from the previous one by doing only a constant number of operations, independent of the substrings' lengths.

</p><p>For example, if we have text "abracadabra" and we are searching for a pattern of length 3, the hash of the first substring, "abr", using 256 as the base, and 101 as the prime modulus is:

</p>

<pre>// ASCII a = 97, b = 98, r = 114.

hash("abr") = [ ( [ ( [ (97 × 256) % 101 + 98 ] % 101 ) × 256 ] % 101 ) + 114 ]  % 101 = 4

</pre>

<p>We can then compute the hash of the next substring, "bra", from the hash of "abr" by subtracting the number added for the first 'a' of "abr", i.e. 97 × 256<sup>2</sup>, multiplying by the base and adding for the last a of "bra", i.e. 97 × 256<sup>0</sup>. Like so:

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .pre-borderless{border:none}

/* end https://en.wikipedia.org/ */

</style><pre class="pre" style="font-size:95%">// <i>old hash (-ve avoider)<sup id="cite_ref-ua_2-0" class="reference"><a href="#cite_note-ua-2"><span class="cite-bracket">[</span>b<span class="cite-bracket">]</span></a></sup> old 'a' left base offset base shift new 'a'</i> prime modulus

hash("bra") = [ ( 4 + 101 - 97 * [(256%101)*256] % 101<sup id="cite_ref-mod101_3-0" class="reference"><a href="#cite_note-mod101-3"><span class="cite-bracket">[</span>c<span class="cite-bracket">]</span></a></sup> ) * 256<sup id="cite_ref-times256_4-0" class="reference"><a href="#cite_note-times256-4"><span class="cite-bracket">[</span>d<span class="cite-bracket">]</span></a></sup> + 97 ] % 101 = 30</pre>

<p>If we are matching the search string "bra", using similar calculation of hash("abr"),

</p>

<pre>hash'("bra") = [ ( [ ( [ ( 98 × 256) %101 + 114] % 101 ) × 256 ] % 101) + 97 ] % 101 = 30

</pre>

<p>If the substrings in question are long, this algorithm achieves great savings compared with many other hashing schemes.

</p><p>Theoretically, there exist other algorithms that could provide convenient recomputation, e.g. multiplying together ASCII values of all characters so that shifting substring would only entail dividing the previous hash by the first character value, then multiplying by the new last character's value. The limitation, however, is the limited size of the integer <a href="Data_type" title="Data type">data type</a> and the necessity of using <a href="Modular_arithmetic" title="Modular arithmetic">modular arithmetic</a> to scale down the hash results.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>e<span class="cite-bracket">]</span></a></sup> Meanwhile, naive hash functions do not produce large numbers quickly, but, just like adding ASCII values, are likely to cause many <a href="Hash_collision" title="Hash collision">hash collisions</a> and hence slow down the algorithm. Hence the described hash function is typically the preferred one in the Rabin–Karp algorithm.

</p>

<div class="mw-heading mw-heading2"><h2 id="Multiple_pattern_search">Multiple pattern search</h2></div>

<p>The Rabin–Karp algorithm is inferior for single pattern searching to <a href="Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a>, <a href="Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a> and other faster single pattern <a href="String_searching_algorithm" class="mw-redirect" title="String searching algorithm">string searching algorithms</a> because of its slow worst case behavior. However, it is a useful algorithm for <a href="String_searching_algorithm" class="mw-redirect" title="String searching algorithm">multiple pattern search</a>.

</p><p>To find any of a large number, say <i>k</i>, fixed length patterns in a text, a simple variant of the Rabin–Karp algorithm uses a <a href="Bloom_filter" title="Bloom filter">Bloom filter</a> or a <a href="Set_data_structure" class="mw-redirect" title="Set data structure">set data structure</a> to check whether the hash of a given string belongs to a set of hash values of patterns we are looking for:

</p>

<div class="mw-highlight mw-highlight-lang-php mw-content-ltr mw-highlight-lines" dir="ltr"><pre><span class="k">function</span> <span class="nf">RabinKarpSet</span><span class="p">(</span><span class="nx">string</span> <span class="nx">s</span><span class="p">[</span><span class="mf">1.</span><span class="o">.</span><span class="nx">n</span><span class="p">],</span> <span class="nx">set</span> <span class="nx">of</span> <span class="nx">string</span> <span class="nx">subs</span><span class="p">,</span> <span class="nx">m</span><span class="p">)</span><span class="o">:</span>

<span class="nx">set</span> <span class="nx">hsubs</span> <span class="o">:=</span> <span class="nx">emptySet</span>

<span class="k">foreach</span> <span class="nx">sub</span> <span class="nx">in</span> <span class="nx">subs</span>

<span class="nx">insert</span> <span class="nb">hash</span><span class="p">(</span><span class="nx">sub</span><span class="p">[</span><span class="mf">1.</span><span class="o">.</span><span class="nx">m</span><span class="p">])</span> <span class="nx">into</span> <span class="nx">hsubs</span>

<span class="k">if</span> <span class="nx">hs</span> <span class="nx">∈</span> <span class="nx">hsubs</span> <span class="k">and</span> <span class="nx">s</span><span class="p">[</span><span class="nx">i</span><span class="o">..</span><span class="nx">i</span><span class="o">+</span><span class="nx">m</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="nx">∈</span> <span class="nx">subs</span>

<span class="k">return</span> <span class="nx">i</span>

<span class="k">return</span> <span class="k">not</span> <span class="nx">found</span>

</pre></div>

<p>We assume all the substrings have a fixed length <i>m</i>.

</p><p>A naïve way to search for <i>k</i> patterns is to repeat a single-pattern search taking O(<i>n</i>+<i>m</i>) time, totaling in O((<i>n</i>+<i>m</i>)<i>k</i>) time. In contrast, the above algorithm can find all <i>k</i> patterns in O(<i>n</i>+<i>km</i>) expected time, assuming that a hash table check works in O(1) expected time.

</p>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-lower-alpha">

<li id="cite_note-mod-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-mod_1-0">^</a></b></span> <span class="reference-text"><span class="nounderlines" style="border: 1px solid var(--border-color-muted,#ddd); color: var(--color-base,#202122); background-color: var( --background-color-neutral-subtle, #fdfdfd); padding: 1px 1px;">%</span> is 'mod' or <a href="Modulo" title="Modulo">modulo</a>, or remainder after integer division, operator.</span>

</li>

<li id="cite_note-ua-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-ua_2-0">^</a></b></span> <span class="reference-text">(-ve avoider) = "underflow avoider". Necessary if using unsigned integers for calculations. Because we know all hashes <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\leq p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\leq p}</annotation>

</semantics>

</math></span><img src="./4ebd776a740ec00d71eb7a2747ac7a54b2942123.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.607ex; height:2.509ex;" alt="{\displaystyle h\leq p}" loading="lazy"></span> for prime modulus <span class="texhtml mvar" style="font-style:italic;">p</span>, we can ensure no underflow by adding <span class="texhtml mvar" style="font-style:italic;">p</span> to the old hash before subtracting the value corresponding to the old 'a' (mod <span class="texhtml mvar" style="font-style:italic;">p</span>).</span>

</li>

<li id="cite_note-mod101-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-mod101_3-0">^</a></b></span> <span class="reference-text">although <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">((256%101)*256)%101</code> is the same as 256<sup>2</sup> mod 101, to avoid overflowing integer maximums when the pattern string is longer (e.g. 'Rabin-Karp' is 10 characters, 256<sup>9</sup> is the offset without modulation ), the pattern length base offset is pre-calculated in a loop, modulating the result each iteration.</span>

</li>

<li id="cite_note-times256-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-times256_4-0">^</a></b></span> <span class="reference-text">the last <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">* 256</code> is the shift of the subtracted hash to the left.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">See <a href="Hash_function" title="Hash function">hash function</a> article.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

</div>

<div class="mw-heading mw-heading3"><h3 id="Sources">Sources</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCandanSapino2010" class="citation book cs1">Candan, K. Selçuk; Sapino, Maria Luisa (2010). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Uk9tyXgQME8C&pg=PA205"><i>Data Management for Multimedia Retrieval</i></a>. Cambridge University Press. pp. <span class="nowrap">205–</span>206. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-88739-7</bdi>.</cite> (for the Bloom filter extension)</li>

<li><cite id="CITEREFCormenLeisersonRivestStein2001" class="citation book cs1"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Rivest, Ronald L.</a>; <a href="Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2001-09-01) [1990]. "The Rabin–Karp algorithm". <i><a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a></i> (2nd ed.). <a href="Cambridge%2C_Massachusetts" title="Cambridge, Massachusetts">Cambridge, Massachusetts</a>: MIT Press. pp. <span class="nowrap">911–</span>916. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-262-03293-3</bdi>.</cite></li>

<li><cite id="CITEREFKarpRabin1987" class="citation journal cs1"><a href="Richard_Karp" class="mw-redirect" title="Richard Karp">Karp, Richard M.</a>; <a href="Michael_O._Rabin" title="Michael O. Rabin">Rabin, Michael O.</a> (March 1987). "Efficient randomized pattern-matching algorithms". <i>IBM Journal of Research and Development</i>. <b>31</b> (2): <span class="nowrap">249–</span>260. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.9502">10.1.1.86.9502</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1147%2Frd.312.0249">10.1147/rd.312.0249</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://courses.csail.mit.edu/6.006/spring11/rec/rec06.pdf">"Rabin–Karp Algorithm/Rolling Hash"</a> <span class="cs1-format">(PDF)</span>. <i>MIT 6.006: Introduction to Algorithms 2011- Lecture Notes</i>. MIT.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Strings176" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Strings176" style="font-size:114%;margin:0 4em"><a href="String_(computer_science)" title="String (computer science)">Strings</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String_metric" title="String metric">String metric</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximate_string_matching" title="Approximate string matching">Approximate string matching</a></li>

<li><a href="Bitap_algorithm" title="Bitap algorithm">Bitap algorithm</a></li>

<li><a href="Damerau%E2%80%93Levenshtein_distance" title="Damerau–Levenshtein distance">Damerau–Levenshtein distance</a></li>

<li><a href="Edit_distance" title="Edit distance">Edit distance</a></li>

<li><a href="Gestalt_pattern_matching" title="Gestalt pattern matching">Gestalt pattern matching</a></li>

<li><a href="Hamming_distance" title="Hamming distance">Hamming distance</a></li>

<li><a href="Jaro%E2%80%93Winkler_distance" title="Jaro–Winkler distance">Jaro–Winkler distance</a></li>

<li><a href="Lee_distance" title="Lee distance">Lee distance</a></li>

<li><a href="Levenshtein_automaton" title="Levenshtein automaton">Levenshtein automaton</a></li>

<li><a href="Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a></li>

<li><a href="Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner–Fischer algorithm </a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String-searching_algorithm" title="String-searching algorithm">String-searching algorithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Apostolico%E2%80%93Giancarlo_algorithm" title="Apostolico–Giancarlo algorithm">Apostolico–Giancarlo algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm" title="Boyer–Moore–Horspool algorithm">Boyer–Moore–Horspool algorithm</a></li>

<li><a href="Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a></li>

<li><a href="Raita_algorithm" title="Raita algorithm">Raita algorithm</a></li>

<li><a href="Trigram_search" title="Trigram search">Trigram search</a></li>

<li><a href="Two-way_string-matching_algorithm" title="Two-way string-matching algorithm">Two-way string-matching algorithm</a></li>

<li><a href="Zhu%E2%80%93Takaoka_string_matching_algorithm" title="Zhu–Takaoka string matching algorithm">Zhu–Takaoka string matching algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Multiple string searching</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick</a></li>

<li><a href="Commentz-Walter_algorithm" title="Commentz-Walter algorithm">Commentz-Walter algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Regular_expression" title="Regular expression">Regular expression</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Comparison_of_regular-expression_engines" class="mw-redirect" title="Comparison of regular-expression engines">Comparison of regular-expression engines</a></li>

<li><a href="Regular_grammar" title="Regular grammar">Regular grammar</a></li>

<li><a href="Thompson's_construction" title="Thompson's construction">Thompson's construction</a></li>

<li><a href="Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">Nondeterministic finite automaton</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Sequence_alignment" title="Sequence alignment">Sequence alignment</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="BLAST_(biotechnology)" title="BLAST (biotechnology)">BLAST</a></li>

<li><a href="Hirschberg's_algorithm" title="Hirschberg's algorithm">Hirschberg's algorithm</a></li>

<li><a href="Needleman%E2%80%93Wunsch_algorithm" title="Needleman–Wunsch algorithm">Needleman–Wunsch algorithm</a></li>

<li><a href="Smith%E2%80%93Waterman_algorithm" title="Smith–Waterman algorithm">Smith–Waterman algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_structure" title="Data structure">Data structure</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">DAFSA</a></li>

<li><a href="Substring_index" title="Substring index">Substring index</a>

<ul><li><a href="Suffix_array" title="Suffix array">Suffix array</a></li>

<li><a href="Suffix_automaton" title="Suffix automaton">Suffix automaton</a></li>

<li><a href="Suffix_tree" title="Suffix tree">Suffix tree</a></li>

<li><a href="Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li>

<li><a href="LCP_array" title="LCP array">LCP array</a></li>

<li><a href="FM-index" title="FM-index">FM-index</a></li></ul></li>

<li><a href="Generalized_suffix_tree" title="Generalized suffix tree">Generalized suffix tree</a></li>

<li><a href="Ternary_search_tree" title="Ternary search tree">Ternary search tree</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parsing" title="Parsing">Parsing</a></li>

<li><a href="Pattern_matching" title="Pattern matching">Pattern matching</a></li>

<li><a href="Compressed_pattern_matching" title="Compressed pattern matching">Compressed pattern matching</a></li>

<li><a href="Longest_common_subsequence" title="Longest common subsequence">Longest common subsequence</a></li>

<li><a href="Longest_common_substring" title="Longest common substring">Longest common substring</a></li>

<li><a href="Sequential_pattern_mining" title="Sequential pattern mining">Sequential pattern mining</a></li>

<li>Sorting</li>

<li><a href="Semi-Thue_system" title="Semi-Thue system">String rewriting systems</a></li>

<li><a href="String_operations" title="String operations">String operations</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-01" href="https://en.wikipedia.org/wiki/?title=Rabin%E2%80%93Karp_algorithm&oldid=1283352644">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>